package com.heima.xiyuanmall.sudoku

/**
 * 设计数独程序所使用的基本数据结构, 以及通用的工具方法
 *
 * [Pos] 描述数独表格中一个单元格的坐标
 * [SudokuCache] 提供解数独需要的工具方法
 *
 * @author flutterdash@qq.com
 * @since 2021/10/2 21:31
 */

typealias Board = Array<IntArray>
typealias SCache = SudokuCache

/** [side] 预设数独表格每一行每一列有9个单元格 */
const val side = 9
/** [candiLimit] 数独每个位置可选的数字位于0~9, 也就是说不超过10, 这个数字用于做缓存数组的初始化大小 */
const val candiLimit = 10

fun emptyBoard(): Board = Array(side) { IntArray(side) { 0 } }

fun defaultTestBoard(): Board = arrayOf(
    intArrayOf(5, 3, 0, 0, 7, 0, 0, 0, 0),
    intArrayOf(6, 0, 0, 1, 9, 5, 0, 0, 0),
    intArrayOf(0, 9, 8, 0, 0, 0, 0, 6, 0),
    intArrayOf(8, 0, 0, 0, 6, 0, 0, 0, 3),
    intArrayOf(4, 0, 0, 8, 0, 3, 0, 0, 1),
    intArrayOf(7, 0, 0, 0, 2, 0, 0, 0, 6),
    intArrayOf(0, 6, 0, 0, 0, 0, 2, 8, 0),
    intArrayOf(0, 0, 0, 4, 1, 9, 0, 0, 5),
    intArrayOf(0, 0, 0, 0, 8, 0, 0, 7, 9)
)

fun getScopeOf(pos: Pos): Collection<Pos> {
    val coll = HashSet<Pos>(32) // cap > (3 * 4) + 9
    coll.addAll(getRowOf(pos))
    coll.addAll(getColOf(pos))
    coll.addAll(getBoxOf(pos))
    return coll
}

private fun getRowOf(pos: Pos): List<Pos> {
    return ArrayList<Pos>(side).apply {
        for (c in 0 until side) {
            add(Pos(pos.row, c))
        }
    }
}

private fun getColOf(pos: Pos): List<Pos> {
    return ArrayList<Pos>(side).apply {
        for (r in 0 until side) {
            add(Pos(r, pos.col))
        }
    }
}

private fun getBoxOf(pos: Pos): List<Pos> {
    val start = Pos(pos.row / 3, pos.col / 3)
    return ArrayList<Pos>(side).apply {
        for (r in 0 until 3) {
            for (c in 0 until 3) {
                add(Pos(start.row + r, start.col + c))
            }
        }
    }
}

data class Pos(
    var row: Int = 0,
    var col: Int = 0
) {
    val finished: Boolean get() = (row == side)

    fun next(): Pos {
        val nextPos = this.copy()
        return if (col + 1 == side) {
            nextPos.newline()
        } else {
            nextPos.apply {
                this@apply.col++
            }
        }
    }

    private fun newline(): Pos {
        row++
        col = 0
        return this
    }

    private fun copy() = Pos(row, col)
}

object SudokuCache {
    private var board: Board = emptyBoard()

    /**
     * 记录数独每一列每一行的已选数字
     */
    private val row = Array(side) { BooleanArray(candiLimit) { false } }
    private val col = Array(side) { BooleanArray(candiLimit) { false } }

    /** [box] 将数独的表格划分为 3 * 3 个大的单元格, 每个box有9个元素, 记录当前区间内已经选过的数字 */
    private val box = Array(3) {
        Array(3) {
            BooleanArray(candiLimit) { false }
        }
    }

    /**
     * 初始化数独缓存
     *
     * 调用此方法是使用 [SudokuCache] 其他方法的前提
     * 同一个数独只需要调用一次
     *
     * @param board 数独表格
     */
    fun init(board: Board) {
        assert(board.size == side && board[0].size == side)
        for (r in board.indices) {
            for (c in board[r].indices) {
                if (board[r][c] in 1..9) {
                    makeMark(r, c, board[r][c])
                } else {
                    removeMark(r, c, board[r][c])
                }
            }
        }
    }

    /**
     * @param pos 一个坐标
     * @return    返回这个坐标可选的数字
     */
    fun candidates(pos: Pos): List<Int> {
        return ArrayList<Int>().apply {
            for (num in 1..9) {
                if (canUse(pos, num)) add(num)
            }
        }
    }

    /**
     * @param pos 一个坐标
     * @param num 一个数字
     * @return    判断这个数字是否可以填在这个坐标上
     */
    fun canUse(pos: Pos, num: Int): Boolean {
        return !(row[pos.row][num] || col[pos.col][num] || box[pos.row/3][pos.col/3][num])
    }

    fun makeMark(pos: Pos, num: Int) = makeMark(pos.row, pos.col, num)
    private fun makeMark(r: Int, c: Int, num: Int) {
        board[r][c] = num
        row[r][num] = true
        col[c][num] = true
        box[r/3][c/3][num] = true
    }

    fun removeMark(pos: Pos, num: Int) = removeMark(pos.row, pos.col, num)
    private fun removeMark(r: Int, c: Int, num: Int) {
        board[r][c] = 0
        row[r][num] = false
        col[c][num] = false
        box[r/3][c/3][num] = false
    }

    fun showAnswer(): Board = board
}